package linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        SingleLinkedList list1 = new SingleLinkedList();

        HeroNode hero1 = new HeroNode(0, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "林冲", "豹子头");
        HeroNode hero3 = new HeroNode(3, "武松", "行者");
        HeroNode hero4 = new HeroNode(4, "花荣", "小李广");
        HeroNode hero5 = new HeroNode(5, "鲁智深", "花和尚");
        HeroNode hero6 = new HeroNode(6, "张青", "菜园子");
        HeroNode hero7= new HeroNode(7, "张青", "菜篮子");

        HeroNode hero11 = new HeroNode(0, "宋江", "及时雨");
        HeroNode hero12 = new HeroNode(2, "林冲", "豹子头");
        HeroNode hero13 = new HeroNode(3, "武松", "行者");
        HeroNode hero14 = new HeroNode(4, "花荣", "小李广");
        HeroNode hero15 = new HeroNode(5, "鲁智深", "花和尚");
        HeroNode hero16 = new HeroNode(6, "张青", "菜园子");
        HeroNode hero17= new HeroNode( 6, "张青", "菜篮子");
        list.addbyorder(hero5);
        list.addbyorder(hero4);
        list.addbyorder(hero6);
        list.addbyorder(hero7);
        list.addbyorder(hero1);
        list.addbyorder(hero2);
        list.addbyorder(hero3);

        list1.addbyorder(hero15);
        list1.addbyorder(hero14);
        list1.addbyorder(hero16);
        list.addbyorder( hero17);
        list1.addbyorder(hero11);
        list1.addbyorder(hero12);
        list1.addbyorder(hero13);
        HeroNode head = list.mergeLinkedList(list1.getHead(), list.getHead());
        list.show(head);
//        System.out.println("更改之前--------------");
//        list.show();
//
//        list.modifyNode(hero7);
//        System.out.println("更改之后--------------");
//        list.show();
//        System.out.println("删除之后--------------");
//        list.delNode(hero6);
//        list.show();
//        System.out.println("链表的长度:"+list.getLength());
//        System.out.println("获取倒数数据:----------");
//        System.out.println(list.getNoLast(1));
//        System.out.println("反转单链表之后--------");
//        list.reverseLinkedList();
//        list.show();
//        System.out.println("利用栈将单链表逆转---------------");
//        list.reversePrint();



    }
}
class SingleLinkedList{
    private HeroNode head= new HeroNode(0,"头结点","阿头");

    public HeroNode getHead() {
        return head;
    }

    //从尾部添加元素
    public void add(HeroNode node){
        //添加元素之前需要找到当前链表的尾部
        HeroNode temp = head;
        while(temp.next!=null){
            temp=temp.next;
        }
        temp.next=node;
    }
    public void addbyorder(HeroNode node) {
        HeroNode temp = head;
        while (temp.next != null) {
            if (temp.next.no > node.no)
                break;
            temp=temp.next;
        }
        node.next=temp.next;
        temp.next=node;
    }
    public void modifyNode(HeroNode node){
        HeroNode temp=head;
        if (temp.next==null){
            System.out.println("链表为空,无法更改");
            return;
        }
        while(temp.next!=null){
           if (temp.no==node.no){
               break;
           }
            temp=temp.next;
        }
        temp.name=node.name;
        temp.nickName=node.nickName;
    }
    public void delNode(HeroNode node){
        HeroNode temp=head;
        if (temp.next==null)
            System.out.println("链表为空,无数据可删");
        while (temp.next!=null){
            if (temp.next.no==node.no)
                break;
            temp=temp.next;
        }
        if (temp.next==null){
            System.out.println("没有找到要删除的节点");
        }else{
            //欲删除的节点是当前节点的下一个节点
            temp.next=temp.next.next;
        }

    }
    public int  getLength(){
        int count=0;
        HeroNode temp=head;
        while(temp.next!=null){
            count++;
            temp=temp.next;
        }
        return count;
    }
    public void show(HeroNode head){
        HeroNode temp=head;
        if (head.next==null){
            System.out.println("链表为空");
            return ;
        }
        while(temp.next!=null){
            temp=temp.next;
            System.out.println(temp);
        }

    }
    public HeroNode getNoLast(int number){
        //获取单链表的导数第number个节点
        HeroNode temp=head;
        int length=getLength();
        if(number>length || number<1){
            System.out.println("数据不合法");
            return null;
        }
        for (int i = 0; i <=length-number; i++) {
            temp=temp.next;
        }
        return temp;

    }
    public void reverseLinkedList(){
        //反转单项链表
        //创建一个反转头结点
        HeroNode reversHead=new HeroNode(0,"反转头结点","反头同志");
        HeroNode temp=head;
        HeroNode temp1=head;
        if (temp.next==null){
            System.out.println("链表为空反转不了");
            return;
        }
        //将指针指向第一个有用节点
        temp=temp.next;
        temp1=temp;
        //遍历链表,然后将遍历所得节点接在反转头结点后
        while(temp.next!=null){
            temp1=temp1.next;
            temp.next=reversHead.next;
            reversHead.next=temp;
            temp=temp1;
        }
        temp.next=reversHead.next;
        reversHead.next=temp;
        //将原来的头结点接在反转节点的后面
        head.next=reversHead.next;
    }
    public void reversePrint(){
        //利用栈对链表进行逆序打印
        if (head.next==null){
            System.out.println("链表为空,无法逆序打印");
            return;
        }
        HeroNode temp=head.next;
        Stack<HeroNode> stack = new Stack<>();
        while(temp!=null){
            stack.push(temp);
            temp=temp.next;
        }
        //逆序打印
        while(stack.size()>0){
            System.out.println(stack.pop());
        }
    }
    public HeroNode mergeLinkedList(HeroNode head1,HeroNode head2){
        //合并两个有序的单链表
        if (head.next==null||head1.next==null){
            System.out.println("存在链表为空");
        }
        HeroNode temp=head1.next;
        HeroNode temp1=head2.next;
        HeroNode nhead=new HeroNode(0,"新头节点","新头");
        HeroNode newtemp=nhead;
        while(temp!=null&&temp1!=null){
            if (temp.no<=temp1.no){
                newtemp.next=temp;
                temp=temp.next;
                newtemp=newtemp.next;
            }else{
                newtemp.next=temp1;
                temp1=temp1.next;
                newtemp=newtemp.next;
            }
        }
        if (temp==null){
            newtemp.next=temp1;
        }else{
            newtemp.next=temp;
        }
        return nhead;
    }
}




class  HeroNode{
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickName = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}